Chris Pollett >
Old Classes >
CS254 |
HW#5 --- last modified February 06 2019 04:07:42..Due date: May 15
Files to be submitted: Purpose: To gain experience with randomized complexity classes, interactive protocols, and circuit lower bounds. Related Course Outcomes: The main course outcomes covered by this assignment are: LO4 -- Know properties of the randomized classes RP, BPP. LO6 -- Be able to explain interactive proof characterizations of classes like PSPACE. LO7 -- Explain at least one circuit lower bound technique such as Razborov's techniques for monotone circuits or switching lemma techniques. Specification: For this homework I would like you to write up solutions to the problems below. If possible, write up the homework in LaTeX. If you use Word, format any math by using the math equation editor. Once you have prepared your solution output it as a PDF and submit it as Hw5.pdf. Be aware that the maximum-sized document that the upload system supports is 10 MB.
Point Breakdown
|